#include "iostream"
#include "vector"
using namespace std;

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> value(1 << n, -1);
        vector<int> freq(n + 1);
        for (int sub = 0; sub < (1 << n); ++sub) {
            // 判断 sub 是否有 n/k 个 1
            if (__builtin_popcount(sub) == n / k) {
                // 使用数组进行计数
                for (int j = 0; j < n; ++j) {
                    if (sub & (1 << j)) {
                        ++freq[nums[j]];
                    }
                }
                // 任意一个数不能出现超过 1 次
                bool flag = true;
                for (int j = 1; j <= n; ++j) {
                    if (freq[j] > 1) {
                        flag = false;
                        break;
                    }
                }
                // 如果满足要求，那么计算 sub 的不兼容性
                if (flag) {
                    int lb = INT_MAX, rb = INT_MIN;
                    for (int j = 1; j <= n; ++j) {
                        if (freq[j] > 0) {
                            lb = min(lb, j);
                            rb = max(rb, j);
                        }
                    }
                    value[sub] = rb - lb;
                }
                // 由于我们使用数组进行计数，因此要将数组恢复原状
                for (int j = 0; j < n; ++j) {
                    if (sub & (1 << j)) {
                        --freq[nums[j]];
                    }
                }
            }
        }
        //上述枚举出所有的集合 并计算 单个集合的不兼容性
        
        vector<int> f(1 << n, -1);
        f[0] = 0;
        for (int mask = 1; mask < (1 << n); ++mask) {
            // 判断 mask 是否有 n/k 倍数个 1
            if (__builtin_popcount(mask) % (n / k) == 0) {
                // 枚举子集
                for (int sub = mask; sub; sub = (sub - 1) & mask) { //计算选定的mask（元素一定的情况下） f[mask]的最小  不兼容性之和
                                                                    //(sub-1)&mask 就是选子集 但不是 所有子集都满足条件  子集的个数应当满足n/k 所以判断 value[sub]!=-1
                                                                    
                    if (value[sub] != -1 && f[mask ^ sub] != -1) {  //f[mask ^ sub] != -1 表示 在选定此sub 剩下的元素不能满足条件

                        if (f[mask] == -1) {
                            f[mask] = f[mask ^ sub] + value[sub];
                        }
                        else {
                            f[mask] = min(f[mask], f[mask ^ sub] + value[sub]);
                        }

                    }

                }
            }
        }
            
        return f[(1 << n) - 1];
    }
};

/*
所以此种做法的思路就是：
一个子集的元素个数是 num=n/k
1.枚举所有 指定个数、无重复的子集
2.动态规划 num整倍数的 最小 不兼容性之后
f[0]
f[num]
f[2*num]
f[3*num]
...
f[k*num]
其思想就是 递增子集个数 / 元素

*/


class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size(), per = n/k;
        if(k == 1) {
            set<int> s(nums.begin(), nums.end());
            if(s.size() < nums.size()) {
                return -1;
            }
            return (*s.rbegin()) - (*s.begin());
        }
        if(k == n) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        int M = (1 << n), dp[M][n];
        memset(dp, 0x3f, sizeof(dp));
        memset(dp[0], 0, sizeof(dp[0]));
        for(int mask = 1; mask < M; ++mask) {
            int cnt = __builtin_popcount(mask), rem = cnt % per;
            if(rem == 0) {
                for(int p = 0; p < n; ++p) {
                    if(mask & (1 << p)) {
                        dp[mask][0] = min(dp[mask][0], dp[mask ^ (1 << p)][p]);
                    }
                }
                for(int pre = 1; pre < n; ++pre) {
                    dp[mask][pre] = dp[mask][0];
                }
            }
            else {
                for(int pre = 0, sum1 = 0; pre < n && cnt - sum1 >= rem; ++pre) { // 剪枝1：剩余的数字得够用来填充当前子集的
                    if(!(mask & (1 << pre))) { // 剪枝2：根据状态转移方程，若 mask & (1 << pre) == 1 则是无效状态，剪掉
                        for(int p = pre + 1; p < n; ++p) {
                            if((mask & (1 << p)) && nums[p] > nums[pre]) {
                                dp[mask][pre] = min(dp[mask][pre], dp[mask ^ (1 << p)][p] + nums[p] - nums[pre]);
                            }
                        }
                    } else {
                        ++sum1;
                    }
                }
            }
        }
        if(dp[M-1][0] >= 10000) {
            return -1;
        }
        return dp[M-1][0];
    }
};


class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int paraCnt=nums.size();
        int subCnt = paraCnt/k;
        int maskCnt=(1<<paraCnt -1);
        vector<int> f(1<<paraCnt,-1);
        vector<int> dp(1<<paraCnt,-1);
        char state = 0;
        for(int mask=1;mask<=maskCnt;++mask){               //枚举大小为subCnt倍数的子集
            int _1_count = __builtin_popcount(mask);

            if(_1_count%subCnt==0){   //
                if(){ //去重
                    break;
                }
                else{ //计算 不兼容性
                    int mult = _1_count/subCnt;
                    if(mult==1){

                        dp[mask]=...;
                    }
                    else{
                        //又要穷举其子 子集 进行状态转移
                        for(int mask2=1;mask2<mask;++mask2){
                            if(__builtin_popcount(mask2)==subCnt){  //选取一个子集
                                if(dp[mask]==-1){
                                    dp[mask]=dp[mask^mask2]+dp[mask2];
                                }
                                else{
                                    dp[mask]=min(dp[mask],dp[mask^mask2]+dp[mask2]);
                                }
                            }
                        }

                    }
                }
            }
        }
    }
};